package com.programmercarl.backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * https://leetcode.cn/problems/palindrome-partitioning/description/
 * 分割回文串
 *
 * @author yulongtian
 * @create 2025-01-10 21:42
 */
public class Test06 {
    public static void main(String[] args) {
        Test06 test06 = new Test06();
        List<List<String>> aab = test06.partition("aab");
        System.out.println(aab);
    }

    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> path = new ArrayList<>();
        backTracking(s, 0, res, path);
        return res;
    }

    public void backTracking(String s, int startIndex, List<List<String>> res, List<String> path) {
        if (startIndex == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s.substring(startIndex, i + 1))) {
                path.add(s.substring(startIndex, i + 1));
            } else {
                continue;
            }
            backTracking(s, i + 1, res, path);
            path.remove(path.size() - 1);
        }

    }

    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

}
